package com.yxp.hard;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Auther : yxpweb
 * @Date : 2021/4/27 17:00
 * @Description: 460. LFU 缓存
 */

public class Problem460 {

    public static void main(String[] args) {

        LFUCache lfuCache = new LFUCache(5);
        lfuCache.put(1, 1);
        lfuCache.put(2, 1);
        lfuCache.put(3, 1);
        lfuCache.put(1, 1);
        lfuCache.put(3, 1);
        lfuCache.put(4, 1);
        lfuCache.put(5, 1);
        lfuCache.put(6, 1);
    }

    static class LFUCache<K, V> {
        int minfreq, capacity;
        // 使用频率表
        Map<Integer, LinkedList<Node>> freq_table;
        // 数据存储表
        Map<K, Node> key_table;

        public LFUCache(int capacity) {
            this.minfreq = 0;
            this.capacity = capacity;
            key_table = new HashMap<K, Node>();
            freq_table = new HashMap<Integer, LinkedList<Node>>();
        }

        public V get(K key) {
            if (capacity == 0) {
                return null;
            }
            if (!key_table.containsKey(key)) {
                return null;
            }
            Node node = key_table.get(key);
            V val = (V) node.val;
            int freq = node.freq;
            freq_table.get(freq).remove(node);
            // 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
            if (freq_table.get(freq).size() == 0) {
                freq_table.remove(freq);
                if (minfreq == freq) {
                    minfreq += 1;
                }
            }
            // 插入到 freq + 1 中
            LinkedList<Node> list = freq_table.getOrDefault(freq + 1, new LinkedList<Node>());
            list.offerFirst(new Node(key, val, freq + 1));
            freq_table.put(freq + 1, list);
            key_table.put(key, freq_table.get(freq + 1).peekFirst());
            return val;
        }

        public void put(K key, V value) {
            if (capacity == 0) {
                return;
            }
            if (!key_table.containsKey(key)) {
                // 缓存已满，需要进行删除操作
                if (key_table.size() == capacity) {
                    // 通过 minFreq 拿到 freq_table[minFreq] 链表的末尾节点
                    Node node = freq_table.get(minfreq).peekLast();
                    key_table.remove(node.key);
                    freq_table.get(minfreq).pollLast();
                    if (freq_table.get(minfreq).size() == 0) {
                        freq_table.remove(minfreq);
                    }
                }
                LinkedList<Node> list = freq_table.getOrDefault(1, new LinkedList<Node>());
                list.offerFirst(new Node(key, value, 1));
                freq_table.put(1, list);
                key_table.put(key, freq_table.get(1).peekFirst());
                minfreq = 1;
            } else {
                // 与 get 操作基本一致，除了需要更新缓存的值
                Node node = key_table.get(key);
                int freq = node.freq;
                freq_table.get(freq).remove(node);
                if (freq_table.get(freq).size() == 0) {
                    freq_table.remove(freq);
                    if (minfreq == freq) {
                        minfreq += 1;
                    }
                }
                LinkedList<Node> list = freq_table.getOrDefault(freq + 1, new LinkedList<Node>());
                list.offerFirst(new Node(key, value, freq + 1));
                freq_table.put(freq + 1, list);
                key_table.put(key, freq_table.get(freq + 1).peekFirst());
            }
        }
    }

    static class Node<K, V> {
        K key;
        V val;
        int freq;

        Node(K key, V val, int freq) {
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    }
}
